#include <stdio.h>
#include <gmp.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

int main(int argc, char **argv) {
  int nuggets_to_collect = (argv[1] ? atoi(argv[1]) : 10);

  int found = 0;
  mpz_t *nuggets = calloc(sizeof(*nuggets), nuggets_to_collect);
  assert(nuggets != NULL);

  mpz_t sum;

  mpz_init(sum);

  mpz_set_ui(sum, 0UL);

  mpz_t delta, a;
  mpz_t step;

  mpz_init(delta);
  mpz_init(a);
  mpz_init(step);

  mpz_set_ui(delta, 20UL);

  mpz_t i;
  mpz_init(i);

  mpz_set_ui(i, 2UL);

  do {
    mpz_mul_ui(step, i, 10UL);
    mpz_add_ui(step, step, 9L);

    mpz_add(delta, delta, step);

/*
    // shortcut: if delta is not of 4k or 4k+1, it is not a square
    if (!mpz_congruent_ui_p(delta, 0UL, 4UL) && !mpz_congruent_ui_p(delta, 1UL, 4UL))
      goto next_step;
*/
    if (mpz_tstbit(delta, 1) != 0)
      goto next_step;

    // is it a square of integer ?
    if (mpz_perfect_square_p(delta) != 0) {
      mpz_t n;
      mpz_init(n);
      mpz_sqrt(n, delta);

      fprintf(stderr, "found a golden nugget: #%02d ", found+1);
      mpz_out_str(stderr, 10, i);
      fprintf(stderr, " - n is ");
      mpz_out_str(stderr, 10, n);
      fprintf(stderr, "\n");

      mpz_init(nuggets[found]);
      mpz_set(nuggets[found], delta);
      found++;

      mpz_add(sum, sum, delta);

      mpz_clear(n);
    }

  next_step:
    mpz_add_ui(i, i, 1UL);
  } while (found < nuggets_to_collect);

  mpz_clear(delta);
  mpz_clear(a);

  return 0;
}
